#include "filesys/cache.h"
#include <string.h>
#include <stdbool.h>
#include "threads/synch.h"
#include "threads/malloc.h"
#include "threads/thread.h"

/* Buffer Cache structure */
struct cache_struct
{
  block_sector_t sector_idx;          /* Block sector ID */
  uint8_t buffer[BLOCK_SECTOR_SIZE];  /* Buffer */
  bool is_accessed;                   /* Accessed status */
  bool is_dirty;                      /* Dirty status */
  int reader_count;                   /* Number of readers */
  int writer_count;                   /* Number of writers */
  struct list_elem elem;              /* Cache 'struct' element */
};

/* Read-ahead structure */
struct read_ahead_struct
{
  block_sector_t sector_idx;          /* Block Sector ID */
  struct list_elem elem;              /* Read-ahead 'struct' element */
};

struct list cache;                    /* File system/Buffer Cache */
struct list read_ahead_list;          /* List of blocks to read-ahead */
struct lock cache_lock;               /* Buffer cache lock */
int cache_index = 0;                  /* Current cache block index */
struct list_elem *ep;                 /* Cache replacement eviction pointer */

/* Function prototypes */
static struct cache_struct *cache_insert (block_sector_t, bool);
static struct cache_struct *cache_lookup (block_sector_t);
static void cache_write_behind (struct cache_struct *cs);
static struct cache_struct *cache_replace (void);
static void cache_bgread (void *);
static void cache_bgwrite (void *);

/* Initialize the file system cache and associated objects */ 
void
cache_init (void)
{
  list_init (&cache);
  list_init (&read_ahead_list);
  lock_init (&cache_lock);
  ep = list_begin (&cache);

  /* Automatically fetch the next block of a file into the cache when one */
  /* block of a file is read, in case that block is about to be read */
  /* Read-ahead is done asynchronously */
  thread_create ("Read-ahead", PRI_DEFAULT, cache_bgread, NULL);

  /* Periodically write all the dirty cache entries back to disk */
  /* Write-back is done asynchronously */
  thread_create ("Write-behind", PRI_DEFAULT, cache_bgwrite, NULL);
}

/* Add a block from the 'FILESYS' block device into the file system cache */ 
static struct cache_struct*
cache_insert (block_sector_t sector_idx, bool read)
{
  ASSERT (sector_idx != INVALID_SECTOR_IDX);

  if (read)
  {
    struct read_ahead_struct *ras = (struct read_ahead_struct *)
                                    malloc (sizeof (struct read_ahead_struct));
    ras->sector_idx = sector_idx + 1;
    list_push_back (&read_ahead_list, &ras->elem);
  }

  lock_acquire (&cache_lock);
  struct cache_struct *cs;
  bool in_cache = false;  

  if (cache_index == CACHE_EXTENT)
  {
    cs = cache_replace ();
    in_cache = true;
  }
  else
    cs = malloc (sizeof (struct cache_struct));

  cs->sector_idx = sector_idx;
  block_read (fs_device, sector_idx, &cs->buffer);
  cs->is_accessed = false;
  cs->is_dirty = false;
  cs->reader_count = 0;
  cs->writer_count = 0;
  
  /* Add to file system cache only if cache replacement didn't take place */
  if (!in_cache)
  {
    list_push_back (&cache, &cs->elem);
    cache_index++;
  }
  lock_release (&cache_lock);

  return cs;
}

/* Look for the block sector 'sector_idx' in the file system cache */
static struct cache_struct*
cache_lookup (block_sector_t sector_idx)
{
  ASSERT (sector_idx != INVALID_SECTOR_IDX);

  lock_acquire (&cache_lock);
  struct list_elem *e;
  for (e = list_begin (&cache); e != list_end (&cache); e = list_next (e))
  {
    struct cache_struct *cs = list_entry (e, struct cache_struct, elem);
    if (cs->sector_idx == sector_idx)
    {
      lock_release (&cache_lock);
      return cs;
    }
  }
  
  lock_release (&cache_lock);
  return NULL;
}

/* Read upto a block from the file system cache */
void
cache_read (block_sector_t sector_idx, void *buffer, size_t offset,
            size_t size)
{
  ASSERT (offset < BLOCK_SECTOR_SIZE);

  struct cache_struct *cs = cache_lookup (sector_idx);
  if (!cs)
    cs = cache_insert (sector_idx, true);

  cs->reader_count++;
  memcpy (buffer, (uint8_t *) &cs->buffer + offset, size);
  cs->is_accessed = true;
  cs->reader_count--;
}

/* Write upto a block to the file system cache */
void
cache_write (block_sector_t sector_idx, void *buffer, size_t offset,
             size_t size)
{
  ASSERT (offset < BLOCK_SECTOR_SIZE);

  struct cache_struct *cs = cache_lookup (sector_idx);
  if (!cs)
    cs = cache_insert (sector_idx, false);
  
  cs->writer_count++;
  memcpy ((uint8_t *) &cs->buffer + offset, buffer, size);
  cs->is_accessed = true;
  cs->is_dirty = true;
  cs->writer_count--;
}

/* Write to 'FILESYS' block device from the file system cache */
static void
cache_write_behind (struct cache_struct *cs)
{
  ASSERT (cs != NULL);

  block_write (fs_device, cs->sector_idx, &cs->buffer);
}

/* Perform cache replacement by using a variant of the Clock algorithm */
static struct cache_struct*
cache_replace (void)
{
  struct cache_struct *cs;
  int pass = 0;  

  while (pass != (CACHE_EXTENT * 2))
  { 
    if (ep == list_end (&cache))
      ep = list_begin (&cache);
    
    /* The crux of this cache replacement algorithm */
    cs = list_entry (ep, struct cache_struct, elem);    
    if (cs->reader_count == 0
        && cs->writer_count == 0
        && !cs->is_accessed)
      break;
    
    /* Give this block sector a second chance and advance */
    cs->is_accessed = false;
    ep = list_next (ep);
    pass++;
  }
  
  /* Perform write behind from file system cache to the disk */
  if (cs->is_dirty)
    cache_write_behind (cs);
 
  return cs;
}

/* Flush the file system cache and deallocate the associated memory */
void
cache_flush (void)
{
  lock_acquire (&cache_lock);
  struct list_elem *e = list_begin (&cache);
  struct cache_struct *cs;
  
  while (e != list_end (&cache))
  {
    cs = list_entry (e, struct cache_struct, elem);
    cache_write_behind (cs);
    e = list_next (e);
  }
  lock_release (&cache_lock);
}

/* Called by a background thread to write the contents of cache periodically */
/* to the file system */
/* Write-behind is done asynchronously */
static void
cache_bgwrite (void *AUX)
{
  while (true)
  {
    cache_flush ();
    timer_sleep (30);
    thread_yield ();
  }
}

/* Called by a background thread to bring the next sector of the file being */
/* read from file system into the cache */
/* Read-ahead is done asynchronously */
static void
cache_bgread (void *AUX)
{
  while (true)
  { 
    struct list_elem *e;
    for (e = list_begin (&read_ahead_list); e != list_end (&read_ahead_list);
         e = list_remove (e))
    {
      struct read_ahead_struct *ras = list_entry
                                      (e, struct read_ahead_struct, elem);
      if (!cache_lookup (ras->sector_idx))
        cache_insert (ras->sector_idx, false);
    }
    
    timer_sleep (30);
    thread_yield ();
  }
}
